import re
replacements = [
(r'(?<=[aeiuo])(u)(?=[aeio])', 'v'),
(r'(qu)', 'kw'),
(r'(y)', 'i'),
(r'^(j)', 'i'),
(r'^(xp)', 'cr'),
(r'(?<=h)(v)(?=[aeiou])', 'u'),
(r'(c)(?=$)', 'k'),
(r'(ck)', 'k'),
(r'^(c)', 'k'),
(r'^(z)', 's'),
(r'^(ih)', 'i'),
(r'^(u)(?=[aeiou])', 'v'),
(r'(v|w)(?=[bcdfgjklmnpstvwyz])', 'u'),
(r'^(v|w)(?=$)', 'u'),
(r'(?<=[bcdfgjklmnpstvwyz]ue)', 'oe'),
(r'(?<=[bcdfgjklmnpstvwyz]ve)', 'oe'),
]

replacements = [ (re.compile(i), j) for i,j in replacements ]

def massage(sound):
    sound = sound.lower()
    for p, r in replacements:
        sound = p.sub(r, sound)
    return sound

def soundex(name, len=7):
    """ soundex
        soundex module conforming to Knuth's algorithm
        implementation 2000-12-24 by Gregory Jorgensen
        public domain
        adapted for Dutch 2011-08-07 Hans Then
    """

    # digits holds the soundex values for the alphabet
    #         abcdefghijklmnopqrstuvwxyz
    #digits ='01230120022455012623010202'
    digits = '01230122002455012673011707'
    sndx = ''
    fc = ''
    fv = ''
    name = massage(name)

    # translate alpha chars in name to soundex digits
    for c in name.upper():
        if c.isalpha():
            if not fc: fc = c   # remember first letter
            if (not fv) and (c in 'AEIOUY'): # and the first vowel
                fv = d = c
            else:
                d = digits[ord(c)-ord('A')]
            # duplicate consecutive soundex digits are skipped
            if not sndx or (d != sndx[-1]):
                sndx += d

    # replace first digit with first alpha character
    sndx = fc + sndx[1:]
    # remove all 0s from the soundex code
    sndx = sndx.replace('0','')
    # return soundex code padded to len characters
    return (sndx + (len * '0'))[:len]

def jacard(s1, s2):
    i = s1 & s2
    u = s1 | s2
    return float(len(i)) / float(len(u))

def levenshtein(a,b):
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    code = []
#    if n > m:
#        # Make sure n <= m, to use O(min(n,m)) space
#        a,b = b,a
#        n,m = m,n

    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)
    else:
       return current[n]

